﻿//2972. 统计移除递增子数组的数目 II
//给你一个下标从 0 开始的 正 整数数组 nums 。
//如果 nums 的一个子数组满足：移除这个子数组后剩余元素 严格递增 ，
//那么我们称这个子数组为 移除递增 子数组。比方说，[5, 3, 4, 6, 7] 中的[3, 4] 是一个移除递增子数组，
//因为移除该子数组后，[5, 3, 4, 6, 7] 变为[5, 6, 7] ，是严格递增的。
//请你返回 nums 中 移除递增 子数组的总数目。
//注意 ，剩余元素为空的数组也视为是递增的。
//子数组 指的是一个数组中一段连续的元素序列。



class Solution {
public:
    long long incremovableSubarrayCount(vector<int>& nums)
    {
        int n = nums.size();
        //统计出严格递增的前缀
        int i = 0;
        while (i < n - 1 && nums[i] < nums[i + 1])
        {
            i++;
        }
        //不保留后缀
        if (i == n - 1)
        { // 每个非空子数组都可以移除
            return (long long)n * (n + 1) / 2;
        }
        long long ans = i + 2;
        //一般情况
        for (int j = n - 1; j == n - 1 || nums[j] < nums[j + 1]; j--)
        {
            while (i >= 0 && nums[i] >= nums[j])
            {
                i--;
            }
            // 可以保留前缀 a[:i+1], a[:i], ..., a[:0] 一共 i+2 个
            ans += i + 2;
        }
        return ans;
    }
};